import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

//˳����࣬ʵ��ADTList<T>�����ķ�����T��ʾ����Ԫ�ص���������
public class SeqList<T> extends Object{
	public static void main(String[] args){
		Integer[] values={70,20,80,30,60};
		SeqList<Integer> list1=new SeqList<Integer>(values);
		Iterator<Integer> it=list1.iterator();
	   
		while(it.hasNext()) {
			int a=it.next();
			System.out.println(a);
			if(a==30) {
				it.remove();
			}
            
		}
		
	    System.out.println(list1.size());
	  
		
	}
	protected Object[] element;//��������洢˳��������Ԫ�أ�������Ա
	protected int n;          //˳���Ԫ�ظ��������ȣ�
	
	public SeqList(int length)  //��������Ϊlength�Ŀձ�
	{
		this.element=new Object[length];   //��������Ĵ洢�ռ䣬Ԫ��Ϊnull
		//��length<0,��java�׳������鳤���쳣
		this.n=0;
	}
	public SeqList()//����Ĭ�������Ŀձ����췽������
	{
		this(64);//���ñ�����������ָ�������б�Ĺ��췽��
	}
	public SeqList(T[] values)//����˳�����values�����ṩԪ��
	{
		this(values.length); //��������Ϊvalues.length�Ŀձ���values==null,�׳��ն����쳣
		for(int i=0;i<values.length;i++)//��������Ԫ�أ�O(n)
			this.element[i]=values[i];   //�������ø�ֵ
			this.n=element.length;
	}
	
	public boolean isEmpty()   //�ж�˳����Ƿ�գ���Ϊ���򷵻�true
	{
		return this.n==0;
	}
	public int size()    //����˳���Ԫ�ظ���
	{
		return this.n;
	}
	public T get(int i)   //���ص�i��Ԫ�أ���iԽ�磬�򷵻�null
	{
		if(i>=0&&i<this.n)
			return(T)this.element[i];    //��������Ԫ�����õĶ��󣬴��ݶ�������
		return null;
	}
	
	//���õ�i��Ԫ��Ϊx��0<i<n,��iԽ�磬���׳����Խ���쳣����x==null�����׳��ն����쳣
	public void set(int i,T x){
		if(x==null)
			throw new NullPointerException("x==null");
		if(i>0&&i<this.n)
			this.element[i]=x;
		else throw new java.lang.IndexOutOfBoundsException(i+"");  //�׳����Խ���쳣
	}
	
	//����˳�������Ԫ�ص������ַ�������ʽΪ����������������Object���toString()����
	public String toString()
	{
		String str=this.getClass().getName()+"(";   //��������
		if(this.n>0)
			str+=this.element[0].toString();
		for(int i=1;i<this.n;i++)
			str+=","+this.element[i].toString();//ִ��T���toString���������ж�̬
		return str+")";    //�ձ���?
	}
	
	//����x��Ϊ��i��Ԫ�أ�x!=null,����x��ţ���x==null,���׳��ն����쳣  O��n��
	//�����i��ȡ�ݴ��ʩ����i<0,�����x����ǰ����i>n,��������
	public int insert(int i,T x)
	{
		if(x==null)
			throw new NullPointerException("x==null");  //�׳��ն����쳣
		if(i<0)   i=0;           //����λ��i�ݴ���������ǰ
		if(i>this.n)   i=this.n;   //���������
		Object[] source =this.element;    //�������ø�ֵ��sourceҲ����element
		if(this.n==element.length)       //����������������˳������������
		{
		   this.element=new Object[source.length*2];   //��������һ���������������
		   for(int j=0;j<i;j++)    //��ֵ��ǰ����Ǯi-1��Ԫ��
			   this.element[j]=source[j];
	    }
		for(int j=this.n-1;j>=i;j--)    //��i��ʼ����β��Ԫ������ƶ�������Ӻ���ǰ
			this.element[j+1]=source[j];
		this.element[i]=x;
		this.n++;
		return i;                       //����x���
	}
	
	//˳���β����xԪ�أ�����x��š���Ա�������ء���������У�this.��1
	public int insert(T x){
		return this.insert(this.n,x);
	}
	

	public T remove1(int i)  //ɾ����i��Ԫ�أ�0<i<n,���ر�ɾ��Ԫ�أ���iԽ�磬�򷵻�null
	{
		if(this.n>0&&i>=0&&i<this.n){
			T old=(T)this.element[i];  //old�д洢��ɾ��Ԫ��
			for(int j=i;j<this.n-1;j++)
				this.element[j]=this.element[j+1];  //Ԫ��ǰ��һ��λ��
			this.element[this.n-1]=null;  //�����������Ϊ�գ��ͷ�ԭ����ʵ��
			this.n--;
			
			
			return old;  
		}
		return null;
	}
	
	public void clear()   //ɾ�����Ա�����Ԫ��
	{
		this.n=0;    //���ó���Ϊ0��δ�ͷ�����ռ�
	}
	
	//˳�������״γ��ֵ���key���Ԫ�أ�����Ԫ�����i,0<=i<n;���Ҳ��ɹ�����-1
	//��key==null����Jjava�׳��ն����쳣NullPointerException
	public int search(T key){
		for(int i=0;i<this.n;i++)
			if(key.equals(this.element[i])) //ִ��T���equals(Object)����������ʱ��̬
				return i;
		return -1;   //�ձ��δ�ҵ�ʱ
	}
	
	//�ж��Ƿ�����ؼ���ΪkeyԪ��
	public boolean contains(T key){
		return this.search(key)!=-1;
	} 
	
	public int insertDifferent(T x)  //���벻�ظ�Ԫ�ء����Ҳ��ɹ�ʱ��β����
	{
		if(this.search(x)==-1){
			return this.insert(this.n,x);
		}
		else  return this.search(x);
			
	}
	public T remove(T key)//ɾ���״γ��ֵ���key��ȵ�Ԫ�أ����ر�ɾ��Ԫ�أ����Ҳ��ɹ�����null
	{
		if(this.search(key)!=-1){
			return this.remove1(this.search(key));
		}
		else return null;
	}
	public boolean equals(Object obj)//�Ƚ�����˳����Ƿ���ȣ�����
	{
		if(this==obj)     //��this��obj����ͬһ��˳���ʵ���������
			return true;
		if(obj instanceof SeqList) //��obj����˳���ʵ����SeqList<?>������SeqList<T>�ĸ���
		{
			SeqList<T> list=(SeqList<T>)obj;  //����listҲ����objҲ���õ�ʵ��
			if(this.n==list.n)     //�Ƚ����߳����Ƿ����
			{
				for(int i=0;i<this.n;i++)   //�Ƚ�����˳��������Ԫ���Ƿ����
					if(!(this.get(i).equals(list.get(i))))    //equals(Object)��������ʱ��̬
						return false;
				return true;
			}
		}
		return false;
	}
	
	//��this֮�����list������Ԫ�أ����ϲ�
	public void addAll(SeqList<?extends T>list)
	{
		
	}
	
	public Iterator<T> iterator(){
		return new Itr();
	}
	 private class Itr implements Iterator<T> 
	{
		 int cursor=0;      
	     ArrayList<T>list=new ArrayList<T>();
	     int number=n;
	     public Itr() {
	    	 for(int i=0;i<n;i++) {
	    		 list.add(get(i));
	    	 }
	     }
		@Override
		public boolean hasNext() {
			// TODO 自动生成的方法存根
			 return cursor != number;//当cursor不等于size时，表示仍有索引元素
		}

		@Override
		public T next() {
			
			return list.get(cursor++);
			
		}
		
		public void remove() {
			int o=cursor-1;
			remove1(o);
		
		}
		 
		 
	 }
	
}
